package com.yuan.leet_note.sort;

import java.util.ArrayList;
import java.util.List;

/**
 * @ClassName: QuickSort
 * @Description: TODO
 * @Author MrYuan
 * @Date: 2021/6/28 16:19
 * @Version 1.0
 */
public class QuickSort {
    //    [5,2,3,1,4]
    private static void quickSort(int[] arr, int left, int right) {
        if (right <= left) return;
        int l = left, r = right, temp = 0, mid = arr[left];
        while (l < r) {
            while (l < r && arr[r] >= mid) {
                r--;
            }
            while (l < r && arr[l] <= mid) {
                l++;
            }
            if (r > l) {
                temp = arr[r];
                arr[r] = arr[l];
                arr[l] = temp;

            }
            arr[left] = arr[l];
            arr[l] = mid;
            quickSort(arr, left, l - 1);
            quickSort(arr, l + 1, right);
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{5, 2, 3, 1, 4};
        quickSort(arr, 0, arr.length - 1);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}